package leetcode;

//给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//candidates 中的每个数字在每个组合中只能使用一次。
//说明：
//所有数字（包括目标数）都是正整数。
//解集不能包含重复的组合。 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

public class problems_040 {

    public static void main(String[] arge) {
        System.out.println(new Solution().combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
    }

    static class Solution {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            for (int cand : candidates) {
                list.add(cand);
            }
            Stack<Integer> stack = new Stack<>();
            findNum( target, stack);
            return ret;
        }

        private void findNum(int target, Stack<Integer> stack) {
            if (target == 0) {
                List<Integer> newList = new ArrayList<>();
                for(Integer index : stack) newList.add(list.get(index));
                newList = newList.stream().sorted().collect(Collectors.toList());
                if (!ret.contains(newList)){
                    ret.add(newList);
                }
            }
            for (int i = 0; i < list.size(); i++) {
                if (stack.contains(i)) continue;
                if (list.get(i) > target) continue;
                stack.push(i);
                findNum(target - list.get(i), stack);
                stack.pop();
            }
        }
    }


//    static class Solution {
//        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//            // 排序
//            Arrays.sort(candidates);
//            for (int i = candidates.length - 1; i >= 0; i--) {
//                // 计算
//                getNext(candidates, i, target, new ArrayList<Integer>());
//            }
////            // 转换显示
////            for (int i = 0; i < listSolution.size(); i++) {
////                for (int j = 0; j < listSolution.get(i).size(); j++) {
////                    if(j != 0) System.out.print(",");
////                    System.out.print(listSolution.get(i).get(j));
////                }
////                System.out.println("");
////            }
//            return listSolution;
//        }
//
//        /**
//         * 回溯法解题
//         */
//        int number = 1;
//        List<List<Integer>> listSolution = new ArrayList<List<Integer>>();
//        public boolean getNext(int[] candidates, int index, int target, List<Integer> solution){
//            // 回溯到底，没算尽，则失败
//            if(index < 0) return false;
//            // 对象
//            int num = candidates[index];
//            if(num == 0){
//                return getNext(candidates, index - 1, target, solution);
//            }
//            System.out.println("当前："+num+"，目标："+target);
//            // 判断处理
//            if(num > target) return getNext(candidates, index - 1, target, solution);
//            candidates[index] = 0;
//            solution.add(num);
//            if(num == target){
//                System.out.println("----一致");
//                listSolution.add(solution);
//                solution = new ArrayList<>();
//                return true;
//            }
//            return getNext(candidates, index - 1, target - num, solution);
//        }
//    }
}
